1. Field of the Invention
The present invention relates to a cache memory and a method of operating the same and, more particularly, to a cache memory using a linear hash function and a method of operating the same.
2. Discussion of Related Art
A hash function is a function for converting a message with an arbitrary size into a message with a fixed size. In particular, a hash function that is a binary linear function expressed by a binary matrix is referred to as a linear hash function or an XOR-based hash function. For example, an arbitrary vector X may be transformed by a linear hash function H as follows:
                                             X            ·            H                    =                    ⁢                                    [                                                x                  3                                ,                                  x                  2                                ,                                  x                  1                                ,                                  x                  0                                            ]                        ·                          (                                                                    1                                                        0                                                                                        0                                                        1                                                                                        1                                                        1                                                                                        0                                                        1                                                              )                                                                    =                    ⁢                      [                                                            x                  3                                ⊕                                  x                  1                                            ,                                                x                  2                                ⊕                                  x                  1                                ⊕                                  x                  0                                                      ]                              
The linear hash function H may be used as a hash function for each bank of a skewed associative cache to increase the hit rate of a cache memory.
The above-mentioned skewed associative cache is a method in which a cache memory is configured with multiple banks to increase a hit rate. In contrast to a set associative cache, the skewed associative cache operates a different hash function among the banks, such that even if data has the same memory address, the banks map the data to different indices. In particular, it is known that a 2-way skewed associative cache using two cache banks results in a higher hit rate than a 4-way set associative cache or a 2-way set associative cache.
In order that the 2-way skewed associative cache may ensure a high hit rate, a method of constructing a pair of linear hash functions having the maximum degree of interbank dispersion and being conflict-free in row, column, diagonal, anti-diagonal, and rectangular patterns has been proposed (H. Vandierendonck and K. De Bosschere, Xor-based hash functions, IEEE Trans. Computers, 54(7), pp. 800-812, 2005). Here, the degree of interbank dispersion between the pair of linear hash functions refers to how small the number of cases, where two values of the pair of hash functions are 0 at the same time, is. Accordingly, when the degree of interbank dispersion is maximum, the number of cases where two values of the pair of hash functions are 0 simultaneously is smallest. As described above, not only the degree of interbank dispersion between the linear hash functions but also conflict avoidance of each linear hash function in row patterns, column patterns, diagonal patterns, anti-diagonal patterns, and rectangular patterns are considered. For example, in order to increase a hit rate, it should be possible to store all data of adjacent memory addresses in a cache memory, which is associated with conflict avoidance in row patterns.
In a pair of linear hash functions, each constructed with a 2m×m binary matrix, when m is an even number, there is proposed the pair of linear hash functions that have the maximum degree of interbank dispersion and avoid conflicts in row, column, diagonal, anti-diagonal, and rectangular patterns. However, when m is an odd number, there is no pair of linear hash functions that meet the above-described requirements, so that construction of a cache memory is limited.